// https://www.lintcode.com/problem/climbing-stairs-ii/

public class Solution {
    /**
     * @param n: An integer
     * @return: An Integer
     */
    public int climbStairs2(int n) {
        // write your code here
        int[] cache = new int[n + 1];
        Arrays.fill(cache, -1);
        cache[0] = 1;
        _climbStairs2(n, cache);
        return cache[n];
    }
    
    protected int _climbStairs2(int n, int[] cache) {
        if (n < 0) {
            return 0;
        }
        if (cache[n] == -1) {
            if (n <= 2) {
                cache[n] = n;
            } else {
                cache[n] = _climbStairs2(n - 1, cache) + _climbStairs2(n - 2, cache) + _climbStairs2(n - 3, cache);
            }
        }
        return cache[n];
    }
}